package Algorithm.string;

/**
 * @Desc:
 * 以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
 * 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将
 * 目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。
 * 请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。
 * 最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
 * 示例 1：
 *
 * 输入："/home/"
 * 输出："/home"
 * 解释：注意，最后一个目录名后面没有斜杠。
 * 示例 2：
 *
 * 输入："/../"
 * 输出："/"
 * 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
 * 示例 3：
 *
 * 输入："/home//foo/"
 * 输出："/home/foo"
 * 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
 * 示例 4：
 *
 * 输入："/a/./b/../../c/"
 * 输出："/c"
 * 示例 5：
 *
 * 输入："/a/../../b/../c//.//"
 * 输出："/c"
 * 示例 6：
 *
 * 输入："/a//b////c/d//././/.."
 * 输出："/a/b/c"
 * @author: cww
 * @DateTime: 2020/4/1 16:01
 */

public class SimplifyPath {
    public static void main(String[] args) throws Exception {
        System.out.println(simplifyPath("/a//b////c/d//././/.."));
//        StringBuilder sb = new StringBuilder();
//        int i = con2(4, "cdfo.../f");
//        System.out.println(i+":"+sb.toString());
    }

    public static String con1(Integer i,String s, StringBuilder sb){
        if(s.charAt(i) != '/'){
            sb.append(s.charAt(i));
            con1(i += 1,s,sb);
            return sb.toString();
        } else {
            return null;
        }
//        return sb.toString();
    }

    public static String simplifyPath(String path){
        long start1 = System.currentTimeMillis();
        String[] pa = new String[path.length()];
        int cur = 0;
        int len = 0;
        for(int i=0;i< (len = path.length());i++){
            if(path.charAt(i) == '.') {
//                if(i + 1 == len) continue;
//                if(path.charAt(i+1) =='.'){
//                    if(cur != 0) cur--;
//                    i++;
//                    continue;
//                } else{
//                    continue;
//                }
                int j = con2(i,path);
                if (j<2) continue;
                if (j == 2) {
                    if(cur != 0) cur--;
                    i++;
                    continue;
                }
                StringBuilder sb = new StringBuilder();
                for(int k=0;k<i;k++){
                    sb.append(".");
                }
                pa[cur++] = sb.toString();
                i += j-1;
                continue;
            }
            if(path.charAt(i) == '/') continue;
            String word = con(i,path,new StringBuilder());
            pa[cur++] = String.valueOf(word);
            i += word.length()-1;
        }

        if(cur == 0) return "/";
        StringBuilder sb = new StringBuilder("/");
        for(int i=0;i<cur;i++){
            sb.append(pa[i]).append("/");
        }
        String s = sb.toString();
        long end1 = System.currentTimeMillis();
        System.out.println(start1 - end1);
        return s.substring(0,s.length()-1);
    }

    public static String con(int i, String path,StringBuilder sb){
        if(path.charAt(i) != '.' && path.charAt(i) != '/'){
            sb.append(path.charAt(i));
            if(i<path.length()-1) con(++i,path,sb);
        } else{
            return null;
        }
        return sb.toString();
    }

    public static int con2(int i, String path){
        if(path.charAt(i)=='.'){
            if (i<path.length()-1) return 1+con2(++i,path);
        }
        return 0;
    }

    /**
     * 消耗1ms
     * @param path
     * @return
     */
    public static String simplifyPath1(String path){
        long start1 = System.currentTimeMillis();
        int pathEnd = 1;
        char[] chars =  path.toCharArray();
        int start = 1;
        int end =1;
        while(end<chars.length){
            if(chars[end]!='/'){
                end++;
            } else{
                if(start == end){
                } else {
                    if(end-start==2&&chars[start]=='.'&&chars[start+1]=='.'){
                        if(pathEnd>1){
                            pathEnd--;
                            while(chars[pathEnd-1]!='/'){
                                pathEnd--;
                            }
                        }
                    } else if(end-start==1&&chars[start]=='.'){
                    } else {
                        for(;start < end; start++){
                            chars[pathEnd] = chars[start];
                            pathEnd++;
                        }
                        chars[pathEnd] = '/';
                        pathEnd++;
                    }
                }
                end++;
                start = end;
            }
        }
        if(end > start){
            if(end-start==2&&chars[start]=='.'&&chars[start+1]=='.'){
                if(pathEnd>1){
                    pathEnd--;
                    while(chars[pathEnd-1]!='/'){
                        pathEnd--;
                    }
                }
            } else if(end-start==1&&chars[start]=='.'){
            } else {
                for(;start < end; start++){
                    chars[pathEnd] = chars[start];
                    pathEnd++;
                }
            }
        }
        if(pathEnd!=1 && chars[pathEnd-1]=='/'){
            pathEnd--;
        }
        long end1 = System.currentTimeMillis();
        System.out.println(start1 - end1);
        return new String(chars, 0, pathEnd);
    }

    public static String simplifyPath3(String path) {
        String[] pa = path.trim().split("/+");
        int cur = 0;
        for(int i=0;i<pa.length;i++){
            if(pa[i].equals("")||pa[i].equals(".")||(pa[i].equals("..") && cur == 0)) continue;
            if(pa[i].equals("..")){
                cur--;
                continue;
            }
            pa[cur++] = pa[i];
        }
        if(cur == 0) return "/";
        StringBuilder sb = new StringBuilder("/");
        for(int i=0;i<cur;i++){
            sb.append(pa[i]).append("/");
        }
        String s = sb.toString();
        return s.substring(0,s.length()-1);
    }

}
